//
// Created by gushen610140 on 2024/4/11.
//

#ifndef DATASTRUCTURECOURSE_GTREE_H
#define DATASTRUCTURECOURSE_GTREE_H

#include <iostream>

template<typename T>
class GNode {
public:
    T data;
    GNode<T> *left;
    GNode<T> *right;

    explicit GNode<T>(T value) : data(value), left(nullptr), right(nullptr) {}
};

template<typename T>
class [[maybe_unused]] GTree {
protected:
    GNode<T> *_root;

    GNode<T> *_createPreorder() {
        T value;
        std::cin >> value;
        if (value == '#')
            return nullptr;
        auto node = new GNode<T>(value);
        node->left = _createPreorder();
        node->right = _createPreorder();
        return node;
    }

    int _getDepth(GNode<T> *node, T value, int depth) {
        // 到头了
        if (node == nullptr)
            return 0;

        // 找到返回深度
        if (node->data == value)
            return depth;

        // 要找的结点在左边
        int leftDepth = _getDepth(node->left, value, depth + 1);
        if (leftDepth != 0)
            return leftDepth;

        // 要找的结点在右边
        int rightDepth = _getDepth(node->right, value, depth + 1);
        if (rightDepth != 0)
            return rightDepth;

        // 没找到返回 0
        return 0;
    }

    int _getDepth(GNode<T> *node) {
        if (node == nullptr)
            return 0;
        return 1 + std::max(_getDepth(node->left), _getDepth(node->right));
    }

    int _getLeaves(GNode<T> *node) {
        if (node == nullptr) {
            return 0;
        }
        if (node->left == nullptr && node->right == nullptr) {
            return 1;
        }
        return _getLeaves(node->left) + _getLeaves(node->right);
    }

    void _printPreorder(GNode<T> *node) {
        if (node == nullptr)
            return;
        std::cout << node->data << ' ';
        _printPreorder(node->left);
        _printPreorder(node->right);
    }

    void _printPostorder(GNode<T> *node) {
        if (node == nullptr) {
            return;
        }
        _printPostorder(node->left);
        _printPostorder(node->right);
        std::cout << node->data;
    }

    void _printInorder(GNode<T> *node) {
        if (node == nullptr) {
            return;
        }
        _printInorder(node->left);
        std::cout << node->data << ' ';
        _printInorder(node->right);
    }

    int _findInorder(std::string &midOrder, T value) {
        for (int i = 0; i < midOrder.size(); i++) {
            if (midOrder[i] == value)
                return i;
        }
        return -1;
    }

    GNode<T> *_createPreInorder(const std::string &preorderStr, std::string &inorderStr,
                                int preOrderStart, int preOrderEnd,
                                int inorderStart, int inorderEnd) {
        if (preOrderStart > preOrderEnd || inorderStart > inorderEnd) {
            return nullptr;
        }
        T value = preorderStr[preOrderStart];
        auto *node = new GNode<T>(value);
        int midIndex = _findInorder(inorderStr, value);
        node->left = _createPreInorder(preorderStr, inorderStr,
                                       preOrderStart + 1,
                                       preOrderStart + midIndex - inorderStart,
                                       inorderStart,
                                       midIndex - 1);
        node->right = _createPreInorder(preorderStr, inorderStr,
                                        preOrderStart + midIndex - inorderStart + 1,
                                        preOrderEnd,
                                        midIndex + 1,
                                        inorderEnd);
        return node;
    }

    GNode<T> *_swap(GNode<T> *node) {
        if (node == nullptr)
            return nullptr;
        _swap(node->left);
        _swap(node->right);
        GNode<T> *temp = node->left;
        node->left = node->right;
        node->right = temp;
        return node;
    }

public:
    GTree() : _root(nullptr) {}

    // 方便子类重写
    [[maybe_unused]] virtual void createPreorder() {
        _root = _createPreorder();
    }

    [[maybe_unused]] int getDepth(T value) {
        return _getDepth(_root, value, 1);
    }

    [[maybe_unused]] int getDepth() {
        return _getDepth(_root);
    }

    [[maybe_unused]] int getLeaves() {
        return _getLeaves(_root);
    }

    [[maybe_unused]] void printPreorder() {
        _printPreorder(_root);
        std::cout << std::endl;
    }

    [[maybe_unused]] void printPostorder() {
        _printPostorder(_root);
        std::cout << std::endl;
    }

    [[maybe_unused]] void printInorder() {
        _printInorder(_root);
        std::cout << std::endl;
    }

    [[maybe_unused]] void createPreInorder(std::string preOrder, std::string midOrder) {
        _root = _createPreInorder(preOrder, midOrder,
                                  0,
                                  preOrder.size() - 1,
                                  0,
                                  midOrder.size() - 1);
    }

    [[maybe_unused]] void swap() {
        _root = _swap(_root);
    }

};


#endif //DATASTRUCTURECOURSE_GTREE_H
